package Preferred_algorithm.Topic7_Divide_and_conquer_algorithm;

import java.util.Random;

public class sort_colors {

    //  75.颜色分类
    //  https://leetcode.cn/problems/sort-colors/

    int[] nums;

    public int[] sortArray(int[] _nums) {
        nums = _nums;
        qsort(0, nums.length - 1);
        return nums;
    }

    public void qsort(int L, int R) {
        if (L >= R) {
            return;
        }

        int key = nums[new Random().nextInt(R - L + 1) + L];

        int left = L - 1, right = R + 1, i = L;
        while (i < right) {
            if (nums[i] < key) {
                swap(left + 1, i);
                left++;
                i++;
            } else if (nums[i] == key) {
                i++;
            } else {
                swap(right - 1, i);
                right--;
            }
        }
        qsort(L, left);
        qsort(right, R);
    }

    public void swap(int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
